This will be a very short video about the convergence of Markov chains. We will not

go into detail in this topic because it's a topic which is very extensive, very advanced

and completely out of scope for this course, but it pays off to build a bit of intuition

because this might help us design good algorithms. Let's look at this Markov chain. It just has

two states, one and two, and with probability one we jump from state one to two and from two to one.

So it's a really easy Markov chain. It always gives us this sequence of states without fear.

It doesn't really have a probability distribution, it's just deterministic already.

And this chain is periodic, so that means propagating a probability vector

gives us the same thing after two applications. That means that, so we haven't talked about this

in detail of course, but sometimes it's interesting to think about how this n times propagation of

probability vectors or densities behaves and whether they converge as measures.

And in this case they can't converge because they're too periodic, so this doesn't converge,

but we still get some kind of convergence for the running average of samples. So one and two and one

and two, so in average we're at state 1.5. So if we were to sample from this Markov chain,

this would still make some kind of sense, but those iterates of distributions,

that's something that doesn't converge. So usually we like our chain to be apyrootic,

so it shouldn't be too regular. We want to have some kind of breakout from

periodic structure such that our Markov chain isn't too well ordered. So that's the first thing.

The second thing is irreducibility. So let's look at this Markov chain. So it's not two Markov chains,

it's one Markov chain, so it's one model, but there are two different components and you cannot

come from one component to the other. So I haven't given you numbers for those transitions, but

they're proper Markov chains, so they stay in one with some probability, then they jump to two with

no probability, but we never go from this cluster of states to that cluster of states and the other

way around. And this is a so-called reducible Markov chain. In that case, we don't have a unique

invariant density. So there's four components, so we can do this concretely, but you can imagine that

you can do something here, you can do something here independently from each other, and it doesn't

change. And if you were to simulate this Markov chain, you start in this point here and you

simulate it a thousand times, then you will only get contributions from one and two. If you start in four and you simulate it a thousand times,

you will only get contributions from three and four. So this sampling idea that we want to do,

which is start somewhere and then simulate the Markov chain, this doesn't work if our Markov chain is reducible.

So those two things, very roughly, very intuitively, are something that we want to

want to have. So it has to be irreducible, so we can go from anywhere to anywhere,

at least in the limit, eventually we can go anywhere, and aperiodic, so our dynamics

is not too regular. If those two things happen, then something happens which might let us think

about mixing. So if we have dough or batter and we put sugar in the batter and then we mix it,

then those two things happen, right? So every corn of sugar goes anywhere, eventually, and

there's nothing periodic going on there, right? It's too complicated, it's really chaotic.

And those ideas of mixing and chaos and this is part of a mathematical theory called ergodic theory,

which is about thinking about dynamics which are complicated but which kind of mix things together

and is strongly connected to the convergence of Markov chains without going too much in detail.

Because that's not my specialty either. So that's very roughly the things that you'd

like to watch out for when designing Markov chain Monte Carlo methods.